package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class DistributeCandies {
    // 2022-08-29 11:10:11
    public static void main(String[] args) {
        Solution solution = new DistributeCandies().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int distributeCandies(int[] candyType) {
//             哈希 + 贪心
//             -105 <= candyType[i] <= 105
//             Map<Integer, Integer> map = new HashMap<>();
//                        for (int j : candyType) {
//                map.put(j, map.getOrDefault(j, 0) + 1);
//            }
            boolean[] map = new boolean[200001];  // 优化哈希表

            int sum = 0;
            for (int j : candyType) {
                if (!map[j + 100000]) {
                    sum++;
                    map[j + 100000] = true;
                }
                if (sum >= candyType.length / 2) {
                    break;
                }
            }
            return sum;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}